package com.wangyadong.hobby.test;

public class BinaryTreeDemo {


    private TreeNode root;

    public BinaryTreeDemo(TreeNode left, TreeNode right, Integer num) {
        root = new TreeNode(num, left, right);
    }

    private BinaryTreeDemo() {
    }

    public void makeEmpty() {
        root = null;
    }

    public boolean contains(TreeNode current, Integer num) {
        if (current == null) {
            return false;
        }
        int compare = num.compareTo(current.element);
        if (compare == 0) {
            return true;
        }
        if (compare < 0) {
            return contains(current.left, num);
        } else {
            return contains(current.right, num);
        }
    }

    public TreeNode findMin(TreeNode treeNode) {
        if (treeNode == null) {
            return null;
        }
        if (treeNode.left == null) {
            return treeNode;
        }
        return findMin(treeNode.left);
    }

    public TreeNode findMax(TreeNode t) {
        if (t != null) {
            while (t.right != null) {
                t = t.right;
            }
        }
        return t;
    }


    public TreeNode insert(TreeNode treeNode, Integer num) {
        if (treeNode == null) {
            return new TreeNode(num, null, null);
        }
        int compareTo = num.compareTo(treeNode.element);
        if (compareTo < 0) {
            treeNode.left = insert(treeNode.left, num);
        } else {
            treeNode.right = insert(treeNode.right, num);
        }
        return treeNode;
    }

    public boolean contanst(Integer num) {
        return contains(root, num);
    }

    private static class TreeNode {
        public Integer element;
        public TreeNode left;
        public TreeNode right;

        public TreeNode() {

        }

        public TreeNode(Integer element, TreeNode left, TreeNode right) {
            this.element = element;
            this.left = left;
            this.right = right;
        }
    }

    public void insert(int i) {
        root = insert(root, i);
    }

    public TreeNode remove(Integer num) {
        return remove(num, root);
    }

    public TreeNode remove(Integer num, TreeNode node) {
        if (node == null) {
            return node;
        }

        int compareTo = num.compareTo(node.element);

        if (compareTo < 0) {
            node.left = remove(num, node.left);
        } else if (compareTo > 0) {
            node.right = remove(num, node.right);
        } else if (node.right != null && node.left != null) {
            TreeNode min = findMin(node.right);
            node.element = min.element;
            node.right = remove(min.element, node);
        } else {
            node = (node.left != null) ? node.left : node.right;
        }
        return node;
    }


    public static void main(String[] args) {
        BinaryTreeDemo binaryTreeDemo = new BinaryTreeDemo();
        binaryTreeDemo.insert(20);
        binaryTreeDemo.insert(90);
        binaryTreeDemo.insert(10);
        binaryTreeDemo.insert(11);
        binaryTreeDemo.insert(1);
        binaryTreeDemo.insert(13);
        binaryTreeDemo.insert(3);
        binaryTreeDemo.remove(100);
        System.out.println(binaryTreeDemo);
        TreeNode min = binaryTreeDemo.findMin(binaryTreeDemo.root);
        System.out.println(min.element == 1);
        TreeNode max = binaryTreeDemo.findMax(binaryTreeDemo.root);
        System.out.println(max.element == 90);
        System.out.println(binaryTreeDemo.contanst(3));
    }


}
